package acwing_05;
import java.util.*;
import java.io.*;
public class _2_01背包问题_2朴素做法优化_carl版 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static int N = 1010;
	static int n,m;// 物品 容积
	static int dp[][] = new int[N][N];
	static int v[] = new int[N];// 体积
	static int w[] = new int[N];//价值
	static StringTokenizer st;
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			v[i] = Integer.parseInt(st.nextToken());
			w[i] = Integer.parseInt(st.nextToken());
		}
		
		// 填充首行
		// i = 物品0的体积 <= 最大体积
		// 小于物品0体积之前的0行<i列都是0
		for(int i = v[0]; i <= m; i++) {
			// 为0行i列赋值物品0的价值
			dp[0][i] = w[0];
		}
		
		for(int i = 1; i < n; i++) { // 物品0的值已经填充过了，直接从1开始
			for(int j = 1; j <= m; j++) { // 容积0的值都是0，直接从1开始
				if(j < v[i]) {
					dp[i][j] = dp[i-1][j];
				}else {
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
				}
			}
		}
		// 直接取最后一个元素的价值就是最大价值
		System.out.println(dp[n-1][m]);
	}
}
